#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include "list.h"
#include <assert.h>

/* Define the structure of a node */
typedef struct Node{
    int priority;     // 优先级
    const void *data; // 报文数据
    struct list_head list;
} Node;

/* Define the head of the list */
typedef struct ListHead{
    struct list_head head;
} ListHead;

// 头节点
extern Node head;
extern Node *priorityIndex[256];

// 初始化全局变量
Node head = {0, NULL, NULL, NULL};
Node *priorityIndex[256] = {NULL};

// 插入新报文到链表中
void insertNode(ListHead *list, int priority, const void *data){
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode){
        printf("Memory allocation failed.\n");
        return;
    }

    newNode->priority = priority;
    newNode->data = data;
    INIT_LIST_HEAD(&newNode->list);

    // 如果是第一个节点，则直接插入到链表尾部
    if (list->head.next == &list->head){
        printf("第一个节点插入到链表尾部 优先级%d\n",priority);
        list_add_tail(&newNode->list, &list->head);
    }
    else
    {
        // 获取链表尾部节点
        Node *tailNode = list_entry(list->head.prev, Node, list);

        // 检查是否是最小优先级
        if (priority > tailNode->priority) {
            printf("最小优先级插入 优先级%d\n",priority);
            // 如果是最小优先级，直接插入到链表尾部
            list_add_tail(&newNode->list, &list->head);
        }
        else
        {
            Node *lastNodeOfSamePriority = priorityIndex[priority];
            if (lastNodeOfSamePriority) {
                printf("相同优先级插入 优先级%d\n",priority);
                // 如果优先级相同，插入到最后一个同优先级的节点后面
                list_add_tail(&newNode->list, lastNodeOfSamePriority->list.next);
            }
            else
            {
                // 否则，按照优先级顺序插入
                printf("优先级顺序插入 优先级%d\n",priority);
                struct list_head *pos = list->head.next;
                while (pos != &list->head && list_entry(pos, Node, list)->priority <= priority) {
                    pos = pos->next;
                }
                list_add_tail(&newNode->list, pos);
            }
        }
    }
    
    // 更新优先级索引中的最后一个节点
    priorityIndex[priority] = newNode;
}

// 释放单个节点
void freeSingleNode(ListHead *list, Node *node)
{
    if (!node)
    {
        return;
    }
    // 获取释放节点的上一个节点
    Node *prevNode = list_entry(node->list.prev, Node, list);

    // 释放节点是优先级索引中的最后一个节点
    if (priorityIndex[node->priority] == node) {
        // 释放节点上一节点与释放节点优先级相同
        if (prevNode->priority == node->priority) {
            priorityIndex[node->priority] = prevNode;
        }
        else
        {
            priorityIndex[node->priority] = NULL;
        }
    }
    list_del(&node->list);
    free(node);
}

// 打印整个链表
void printList(ListHead *list)
{
    printf("List:\n");
    struct list_head *pos = list->head.next;
    while (pos != &list->head) {
        Node *node = list_entry(pos, Node, list);
        printf("Priority: %d, Data: %s\n", node->priority, (const char *)node->data);
        pos = pos->next;
    }
}

// 辅助函数：检查链表是否按优先级排序
static void check_sorted(ListHead *list) {
    struct list_head *pos = list->head.next;
    int last_priority = -1;
    while (pos != &list->head) {
        Node *node = list_entry(pos, Node, list);
        assert(node->priority >= last_priority);
        last_priority = node->priority;
        pos = pos->next;
    }
}

// 辅助函数：查找具有指定数据的节点
static Node *find_node(ListHead *list, int priority, const char *data) {
    Node *pos;
    list_for_each_entry(pos, &list->head, list) {
        if (strcmp((const char *)pos->data, data) == 0 && pos->priority == priority) {
            return pos;
        }
    }
    return NULL;
}

/************************ 测试函数 **************************/

// 插入节点测试
void testInsertNodes(ListHead *list) {
    insertNode(list, 100, "Hello");
    insertNode(list, 200, "World");
    insertNode(list, 150, "Hi");
    insertNode(list, 150, "Bye");
    insertNode(list, 50, "Low");
    insertNode(list, 200, "high");
    insertNode(list, 150, "Bye1");

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 200, "World") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 150, "Bye") != NULL);
    assert(find_node(list, 50, "Low") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);  

    printf("插入节点测试结果:\n");
    printList(list);
    printf("Insertion tests passed.\n");
}

// 删除第一个节点测试
void testDeleteNode(ListHead *list) {
    Node *nodeToFree = NULL;
    Node *pos;
    list_for_each_entry(pos, &list->head, list) {
        if (pos->priority == 200 && strcmp((const char *)pos->data, "World") == 0) {
            nodeToFree = pos;
            break;
        }
    }
    if (nodeToFree) {
        freeSingleNode(list, nodeToFree);
    }

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 150, "Bye") != NULL);
    assert(find_node(list, 50, "Low") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);  

    printf("删除节点测试结果:\n");
    printList(list);
}

// 删除中间节点测试
void testDeleteMiddleNode(ListHead *list) {
    Node *nodeToFree = NULL;
    Node *pos;
    list_for_each_entry(pos, &list->head, list) {
        if (pos->priority == 150 && strcmp((const char *)pos->data, "Bye") == 0) {
            nodeToFree = pos;
            break;
        }
    }
    if (nodeToFree) {
        freeSingleNode(list, nodeToFree);
    }

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 50, "Low") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);  

    printf("删除节点测试结果:\n");
    printList(list);
}

// 删除最后一个节点测试
void testDeleteLastNode(ListHead *list) {
    Node *nodeToFree = NULL;
    Node *pos;
    list_for_each_entry(pos, &list->head, list) {
        if (pos->priority == 50 && strcmp((const char *)pos->data, "Low") == 0) {
            nodeToFree = pos;
            break;
        }
    }
    if (nodeToFree) {
        freeSingleNode(list, nodeToFree);
    }

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);  

    printf("删除节点测试结果:\n");
    printList(list);
}

// 添加一个更小的优先级节点测试
void testInsertLowerPriorityNode(ListHead *list) {
    insertNode(list, 5, "Low");

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);
    assert(find_node(list, 5, "Low") != NULL);  

    printf("添加一个更小的优先级节点测试结果:\n");
    printList(list);
}

// 添加一个更大的优先级节点测试
void testInsertHigherPriorityNode(ListHead *list) {
    insertNode(list, 201, "High");

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);
    assert(find_node(list, 5, "Low") != NULL);
    assert(find_node(list, 201, "High") != NULL);

    printf("添加一个更大的优先级节点测试结果:\n");
    printList(list);
}

// 释放优先级5的节点测试
void testFreeNode(ListHead *list) {
    Node *nodeToFree = NULL;
    Node *pos;
    list_for_each_entry(pos, &list->head, list) {
        if (pos->priority == 5 && strcmp((const char *)pos->data, "Low") == 0) {
            nodeToFree = pos;
            break;
        }
    }
    if (nodeToFree) {
        freeSingleNode(list, nodeToFree);
    }

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 200, "high") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);
    assert(find_node(list, 201, "High") != NULL);

    printf("释放优先级5的节点测试结果:\n");
    printList(list);
}

// 释放全部节点测试
void testFreeAllNodes(ListHead *list) {
    Node *nodeToFree = NULL;
    int i = 1;
    struct list_head *pos1 = NULL, *q = NULL;
    list_for_each_safe(pos1, q, &list->head) {
        Node *currentNode = list_entry(pos1, Node, list);
        freeSingleNode(list, currentNode);
        printf("释放第%d个节点\n", i++);
    }
    printf("释放全部节点测试结果:\n");
    printList(list);
}

// 重新添加节点测试
void testReinsertNodes(ListHead *list) {
    insertNode(list, 100, "Hello");
    insertNode(list, 200, "World");
    insertNode(list, 150, "Hi");
    insertNode(list, 150, "Bye");
    insertNode(list, 50, "Low");
    insertNode(list, 200, "Low");
    insertNode(list, 150, "Bye1");
    insertNode(list, 150, "666");
    insertNode(list, 150, "777");

    // 检查链表是否按优先级排序
    check_sorted(list);

    // 检查每个节点是否存在
    assert(find_node(list, 100, "Hello") != NULL);
    assert(find_node(list, 200, "World") != NULL);
    assert(find_node(list, 150, "Hi") != NULL);
    assert(find_node(list, 150, "Bye") != NULL);
    assert(find_node(list, 50, "Low") != NULL);
    assert(find_node(list, 200, "Low") != NULL);
    assert(find_node(list, 150, "Bye1") != NULL);
    assert(find_node(list, 150, "666") != NULL);
    assert(find_node(list, 150, "777") != NULL);

    printf("重新添加节点测试结果:\n");
    printList(list);
}

int main()
{
    ListHead list;
    INIT_LIST_HEAD(&list.head);

    printf("\n[1]初始化链表测试结果:\n");
    testInsertNodes(&list);

    printf("\n[2]删除第一个节点测试结果:\n");
    testDeleteNode(&list);

    printf("\n[3]删除中间节点测试结果:\n");
    testDeleteMiddleNode(&list);

    printf("\n[4]删除最后一个节点测试结果:\n");
    testDeleteLastNode(&list);

    printf("\n[5]添加一个更小的优先级节点测试结果:\n");
    testInsertLowerPriorityNode(&list);

    printf("\n[6]添加一个更大的优先级节点测试结果:\n");
    testInsertHigherPriorityNode(&list);

    printf("\n[7]释放优先级5的节点测试结果:\n");
    testFreeNode(&list);

    printf("\n[8]释放全部节点测试结果:\n");
    testFreeAllNodes(&list);

    printf("\n[9]重新添加节点测试结果:\n");
    testReinsertNodes(&list);

    printf("\n链表测试结束\n");

    return 0;
}